package 剑指Offer.中等;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [4,1,4,6]
 * 输出：[1,6] 或 [6,1]
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,10,4,1,4,3,3]
 * 输出：[2,10] 或 [10,2]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/9/5 10:58
 */
public class _56I数组中数字出现的次数 {

    public int[] singleNumbers(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }

        }
        List<Integer> list = new ArrayList<>();
        for (Integer i : set) {
            list.add(i);
        }
        return list.stream().mapToInt(x -> x).toArray();
    }

    public static void main(String[] args) {
        _56I数组中数字出现的次数 a = new _56I数组中数字出现的次数();

        a.singleNumbersV2(new int[]{4, 1, 4, 3});
    }

    /**
     * 使用异或可以将所有的相同的数字给去除掉
     */
    public int[] singleNumbersV2(int[] nums) {
        int n = 0;
        // 找到 x^y 的结果
        for (int num : nums) {
            n ^= num;
        }
        int m = 1;
        // 找到 x^y 第一个异或等于1的数
        while ((m & n) == 0) {
            m <<= 1;
        }
        // 根据 m 的第一位进行分组
        int x = 0, y = 0;
        for (int num : nums) {
            if ((num & m) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }

}
